package dp;

import org.junit.Test;

/**
 * @Description 连续子数组的最大和 https://leetcode.cn/problems/maximum-subarray/
 * @Author Firenut
 * @Date 2022-11-28 19:55
 */
public class T42_maxSubArray {
    @Test
    public void test() {
//        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        int[] nums = {1};
        int[] nums = {5, 4, -1, 7, 8};
        maxSubArray2(nums);
    }

    // 扩展 如何求"最大和的连续子数组的左右下标"?
    public int maxSubArray2(int[] nums) {
        int start = 0, end = 0;         // 标识最大和的连续子数组的左右下标
        int subStart = 0, subEnd = 0;   // 标识某个子数组的左右下标
        int max = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
                subEnd = i;
            }else {
                subStart = subEnd = i;
            }
            if (nums[i] > max) { // 更新下标
                start = subStart;
                end = subEnd;
                max = nums[i];
            }
//          max = Math.max(max, nums[i]);
        }
        System.out.println("[" + start + "," + end + "]");
        return max;
    }


    //法1:采用双指针遍历，时间复杂度为O(n^2),而题目要求时间复杂度为O(n)
    //法2:动态规划
    //思路:
    // 状态定义:
    //  定义dp[i]表示以nums[i]为结尾的连续子数组最大和,必须包含nums[i],才能保证dp[i] 到 dp[i+1]的连续性
    // 转移方程:
    //  如果dp[i-1]<0,则dp[i] = nums[i]
    //  如果dp[i-1]>0,则dp[i] = dp[i-1]+nums[i]
    // 初始值:
    //  dp[0]=nums[0]
    //  返回值:
    //    遍历数组,返回dp数组的最大值

    //优化:由于dp[i]只与dp[i-1]、nums[i]有关系，可以直接将nums数组当做dp数组来用，从而将空间复杂度降为O(1)
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
            }
            max = Math.max(max, nums[i]);
        }
        return max;
    }
}
